package com.lw.leetcode.dp.c;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * c
 * dp
 * 2218. 从栈中取出 K 个硬币的最大面值和
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/1 11:35
 */
public class MaxValueOfCoins {


    public static void main(String[] args) {
        MaxValueOfCoins test = new MaxValueOfCoins();

        // 101
        List<List<Integer>> piles = new ArrayList<List<Integer>>() {{
            add(Arrays.asList(1, 100, 3));
            add(Arrays.asList(7, 8, 9));
        }};
        int k = 2;

        // 706
//        List<List<Integer>> piles = new ArrayList<List<Integer>>(){{
//           add(Arrays.asList(100));
//           add(Arrays.asList(100));
//           add(Arrays.asList(100));
//           add(Arrays.asList(100));
//           add(Arrays.asList(100));
//           add(Arrays.asList(100));
//           add(Arrays.asList(1,1,1,1,1,1,700));
//        }};
//        int k = 7;

        int i = test.maxValueOfCoins(piles, k);
        System.out.println(i);
    }

    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int size = piles.size();
        int[][] arr = new int[size][k + 1];
        List<Integer> list = piles.get(0);
        int length = list.size();
        int min = Math.min(length, k);
        for (int j = 1; j <= min; j++) {
            arr[0][j] = list.get(j - 1) + arr[0][j - 1];
        }
        int all = length;
        for (int i = 1; i < size; i++) {
            list = piles.get(i);
            length = list.size();
            all += length;
            min = Math.min(all, k);
            for (int j = 1; j <= min; j++) {
                int sum = 0;
                int m = Math.min(length, j);
                arr[i][j] = arr[i - 1][j];
                for (int n = 1; n <= m; n++) {
                    sum += list.get(n - 1);
                    arr[i][j] = Math.max(arr[i][j], arr[i - 1][j - n] + sum);
                }
            }
        }
        return arr[size - 1][k];
    }

}
